package acwing.数学.欧拉;

import java.util.Scanner;

/**
 * 欧拉函数
 *
 * @author yang
 * @date 2022/1/16
 */
public class 欧拉函数 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        while (n-- > 0) {
            int x = sc.nextInt();
            int s = ol(x);
            System.out.println(s);
        }
    }

    private static int ol(int x) {
        int res = x;
        for (int i = 2; i <= x / i; i++) {

            if (x % i == 0) {
                res = res / i * (i - 1);
                while (x % i == 0) x /= i;
            }
        }
        if (x > 1) res = res / x * (x - 1);
        return x;
    }
}
